import com.sun.media.sound.DLSInfo;
import org.w3c.dom.ls.LSInput;

import java.util.*;

class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};

public class project {
    public int clumsy(int n) {
        Stack<Integer> stack=new Stack<>();
        stack.add(n);
        n--;
        int index=0;
        while (n>0){
            if(index%4==0){
                stack.add(stack.pop()*n);
            }else if(index%4==1){
                stack.add(stack.pop()/n);
            }else if(index%4==2){
                stack.add(n);
            }else{
                stack.add(-n);
            }
            n--;
            index++;
        }
        int ret=0;
        while (!stack.isEmpty()){
            ret+=stack.pop();
        }
        return ret;
    }

















    List<Integer> l=new ArrayList<>();
    List<List<Integer>> list=new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        dfs(false,0,nums);
        return list;
    }
    public void dfs(boolean flag,int index,int[] nums){
        if(index==nums.length){
            list.add(new ArrayList<>(l));
        }
        dfs(false,index+1,nums);
        if(!flag&&index>0&&nums[index-1]==nums[index]){
            return;
        }
        l.add(nums[index]);
        dfs(true,index+1,nums);
        l.remove(l.size()-1);
    }

















    public boolean checkIfCanBreak(String s1, String s2) {
        int[] arr1=new int[26];
        int[] arr2=new int[26];
        for(int i=0;i<s1.length();i++){
            arr1[s1.charAt(i)-'a']++;
            arr2[s2.charAt(i)-'a']++;
        }
        int flag=0;
        int len1=s1.length();
        int len2=s2.length();
        for(int i=0;i<26;i++){
            len1-=arr1[i];
            len2-=arr2[i];
            if(len1<len2&&flag==0){
                flag=1;
            }else if(len1>len2&&flag==0){
                flag=-1;
            }else if(len1<len2&&flag==-1){
                return false;
            }else if(len1>len2&&flag==1){
                return false;
            }
        }
        return true;
    }















    Set<String> set=new HashSet<>();
    public boolean reorderedPowerOf2(int n) {
        find();
        return set.contains(cont(n));
    }
    public void find(){
        for(int i=1;i<=1e9;i<<=1){
            set.add(cont(i));
        }
    }
    public String cont(int n){
        char[] str=new char[10];
        while (n>0){
            str[n%10]++;
            n/=10;
        }
        return new String(str);
    }












    public int numSimilarGroups(String[] strs) {
        int n=strs.length;
        int[] father=new int[n];
        for(int i=0;i<n;i++){
            father[i]=i;
        }
        int ret=n;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(Similar(strs[i],strs[j])&&union(father,i,j)){
                    ret--;
                }
            }
        }
        return ret;
    }
    public boolean Similar(String s1,String s2){
        int count=0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)!=s2.charAt(i)){
                count++;
            }
        }
        return count<3;
    }
    public boolean union(int[] father,int i,int j){
        int x=findFather(father,i);
        int y=findFather(father,j);
        if(x!=y){
            father[x]=y;
            return true;
        }
        return false;
    }
    public int findFather(int[] father,int index){
        if(father[index]!=index){
            father[index]=findFather(father,father[index]);
        }
        return father[index];
    }















    public int numSimilarGroups1(String[] strs) {
        int len=strs.length;
        int[] fathers=new int[len];
        int ret=len;
        for(int i=0;i<len;i++){
            fathers[i]=i;
        }
        for(int i=0;i<len;i++){
            for(int j=i+1;j<len;j++){
                if(Similar1(strs[i],strs[j])&&findFather1(fathers,i,j)){
                    ret--;
                }
            }
        }
        return ret;
    }
    public boolean Similar1(String s1,String s2){
        int count=0;
        for(int i=0;i<s1.length();i++){
            if(s1.charAt(i)!=s2.charAt(i)){
                count++;
            }
        }
        return count<3;
    }
    public boolean findFather1(int[] fathers,int i,int j){
        int x=find1(fathers,i);
        int y=find1(fathers,j);
        if(x!=y){
            fathers[x]=y;
            return true;
        }
        return false;
    }
    public int find1(int[] fathers,int index ){
        if(fathers[index]!=index){
            fathers[index]=find1(fathers,fathers[index]);
        }
        return fathers[index];
    }



















    public int minSetSize(int[] arr) {
        Map<Integer,Integer> map=new HashMap<>();
        int n=arr.length;
        for(int i=0;i<n;i++){
            map.put(arr[i],map.getOrDefault(arr[i],0)+1);
        }
        int count=0;
        int[] nums=new int[map.size()];
        int index=0;
        int sum=0;
        for(int num:map.values()){
            nums[index++]=num;
        }
        Arrays.sort(nums);
        for(int i=nums.length-1;i>=0;i--){
            sum+=nums[i];
            n-=nums[i];
            count++;
            if(sum>=n){
                break;
            }
        }
        return count;
    }

















    public int[][] kClosest(int[][] points, int k) {
        Arrays.sort(points, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return (o1[0]*o1[0]+o1[1]*o1[1])-(o2[0]*o2[0]+o2[1]*o2[1]);
            }
        });
        return Arrays.copyOfRange(points,0,k);
    }

















    public int minSideJumps(int[] obstacles) {
        int len=obstacles.length;
        int current=2;
        int i=0;
        int count=0;
        while (i<len-1){
            int tmp=current;
            int j=i;
            if(obstacles[i+1]==current){
                count++;
                while (j<=len-1){
                    if(obstacles[j]==0||obstacles[j]==current){
                        j++;
                    }else if(obstacles[j]==3){
                        if(current==2){
                            current=1;
                            break;
                        }else{
                            current=2;
                            break;
                        }
                    }else if(obstacles[j]==2){
                        if(current==3){
                            current=1;
                            break;
                        }else{
                            current=3;
                            break;
                        }
                    }else{
                        if(current==2){
                            current=3;
                            break;
                        }else{
                            current=2;
                            break;
                        }
                    }
                }
                if(current==tmp){
                    current=(current+1)%3+1;
                }
            }else{
                j++;
            }
            i=j;
        }
        return count;
    }











    List<Integer> list1=new ArrayList<>();
    public List<Integer> postorder(Node root) {
        if(root==null){
            return list1;
        }
        for(Node node:root.children){
            if(node!=null){
                postorder(node);
            }
        }
        list1.add(root.val);
        return list1;
    }
}
